/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/lowest-common-ancestor-ii
   @Language: C++
   @Datetime: 19-04-08 11:58
   */

/**
 * Definition of ParentTreeNode:
 * class ParentTreeNode {
 * public:
 *     int val;
 *     ParentTreeNode *parent, *left, *right;
 * }
 */


class Solution {
public:
	/*
	 * @param root: The root of the tree
	 * @param A: node in the tree
	 * @param B: node in the tree
	 * @return: The lowest common ancestor of A and B
	 */
	ParentTreeNode * lowestCommonAncestorII(ParentTreeNode * root, ParentTreeNode * A, ParentTreeNode * B) {
		// write your code here
		stack<ParentTreeNode*> sa, sb;
		for(; A!=root; A=A->parent)
			sa.push(A);
		for(; B!=root; B=B->parent)
			sb.push(B);
		for(; sa.size() && sb.size() && sa.top()==sb.top(); sa.pop(),sb.pop())
			root=sa.top();
		return root;
	}
};
